package string;

/**
 * Class to generate all the combinations of a string 
 * 
 * Timing complexity: O(2^n - 1)
 * 
 * This logic is equivalent to depth first traversal of below shown 
 * tree. (Breadth first traversal will also give the result)
 * 
 * 				root
 * 				/ | \
 * 			 a / b| c\
 * 	          /   |   \
 * 	 	   node  node  leaf 
 * 	    	/ |   |
 * 		 b / c|  c|
 * 		  /   |   |
 * 	    node leaf leaf
 * 	    / 
 * 	 c /	 
 * 	  /
 *  leaf  
 * 
 * */
public class Combinations {

	public static void combine(String instr, StringBuffer outstr, int index)
	{
		for (int i = index; i < instr.length(); i++)
		{
			outstr.append(instr.charAt(i));
			System.out.println(outstr);
			combine(instr, outstr, i + 1);
			outstr.deleteCharAt(outstr.length() - 1);
		}
	} 

	public static void main(String[] args){
		combine("abc", new StringBuffer(), 0);
	}
}
